P4177 [CEOI2008]order

发布于 2020-12-26 | 分类于最大点权闭合子图、网络流 | 4分钟 | 562字数

如果没有租用机器这一操作，做法同 P2762 太空飞行计划问题，用最大权闭合子图模型解决。

考虑如何在经典方法构造的新图中体现租用机器这一操作。

新图中对于工作和它所需的机器之间的容量为 $+\infty$ , 意义即为选择这个工作就必须购买这个机器。

阅读全文 »

Dilworth 定理

发布于 2020-12-23 | 分类于图论 | 2分钟 | 418字数

一.一些定义

1.偏序集

若一个集合 $A$ , 满足一种关系 $\le$ ，且满足

阅读全文 »

CF1215F Radio Stations

发布于 2020-12-12 | 分类于 2-SAT 、优化建图 | 4分钟 | 688字数

令 $u$ 表示选择电站 $u$ , $u'$ 表示不选择电站 $u$ 。

首先可以简单的处理出电站之间的要求：

阅读全文 »

P4983 忘情

发布于 2020-11-30 | 分类于斜率优化、 wqs二分 | 5分钟 | 759字数

题目传送门 & 更好的体验

首先看一下每段的值：

\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}

阅读全文 »

CF113D Museum

发布于 2020-11-27 | 分类于高斯消元、概率dp | 5分钟 | 691字数

f_{i,j}

：两人分别在房间

i,j

的概率。初始状态

f_{a,b}=1

f_{i,j}=p_ip_jf_{i,j}+\sum_{(i,u) \in E}\sum_{(j,v) \in E} \frac{1-p_u}{\deg_u} \frac{1-p_v}{\deg_v}f_{u,v}

阅读全文 »

P3211 [HNOI2011]XOR和路径

发布于 2020-11-27 | 分类于高斯消元、概率dp | 4分钟 | 606字数

异或的期望不能直接算，对每一位单独考虑。

$f[u][0/1]$ :节点 $u$ 的第 $i$ 位为 $0/1$ 的概率。

注意经过节点 $u$ 的概率不一定为 $1$ ，所以 $f[u][0]+f[u][1]$ 的值不一定为 $1$ 。

阅读全文 »

2020.11.20 模拟赛

发布于 2020-11-25 | 分类于模拟赛、线段树、数论、图论 | 8分钟 | 1513字数

\text{T1}

Subtask 1 40 pts

阅读全文 »

CF575A Fibonotci

发布于 2020-11-25 | 分类于矩阵乘法、线段树 | 1分钟 | 164字数

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵，可以暴力计算。

我们知道矩阵乘法有结合律，那么两次修改之间的矩阵可以快速求出乘积。

阅读全文 »

P5437 [XR-2]约定

发布于 2020-11-25 | 分类于拉格朗日插值 | 6分钟 | 889字数

每一条边被选中的概率： $\frac{n-1}{\frac{n(n-1)}{2}}=\frac{2}{n}$

所以答案为：

\frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (i+j)^k

阅读全文 »

P5929 [POI1999]地图

发布于 2020-11-25 | 分类于 dp | 3分钟 | 480字数

至少有一半不小于

A(k)

, 至少有一半不大于

A(k)

所以 $A(k)$ 应该是选出的区域人口的中位数。

为了使误差尽可能小，每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »